package com.jxb.sort;

import java.util.Arrays;

/**
 * 计数排序
 * 1：先构建计数数组：遍历原数组，获取最大值+1，为数组长度
 * 2：嵌套遍历(外计数数组，内原数组),填充计数数组
 * 3：遍历计数数组，调整原数组
 *
 * @author jiaobo
 * @date Created in 2024/12/12 20:32
 **/
public class CountSort {

    public static void main(String[] args) {
        int[] nums = {1,4,3,6,0,4,5,9,4,2,6};
        System.out.println("排序开始----------------->" + Arrays.toString(nums));
        int[] res = sortArray(nums);
        System.out.println("排序结束----------------->" + Arrays.toString(res));
    }


    public static int[] sortArray(int[] nums) {
        //构建计数数组
        int max = 0;
        for (int i = 0;i<nums.length;i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
        }
        max = max +1;
        int[] countArray = new int[max];

        //再次进行遍历，填充计数数组
        for (int j = 0;j<max;j++) {
            for (int i = 0;i<nums.length;i++) {
               if (j == nums[i]) {
                   countArray[j] = countArray[j] +1;
               }
            }
        }

        //遍历填充后的计数数组，调整原数组数据
        int i = 0;
        for (int j = 0;j<max;j++) {
            int cs = countArray[j];
            while (cs > 0 && i<nums.length) {
                nums[i] = j;
                i++;
                cs--;
            }
        }
        return nums;
    }

}
